package org.hhchat.leetcode.dp;

/**
 * Created this one by HMH on 2017/6/12.
 * 上升期和下降期
 * 上升期如果遇到更大的，则替换最后一个，继续等待小的出现
 * 下降期如果遇见更小的，则替换最后一个，继续等待大的出现
 * 最开始去除所有相同的，直到出发第一个波动，开始上述操作，直到结束
 */
public class code376 {
    public static class Solution {
        public int wiggleMaxLength(int[] nums) {
            //边界条件
            if(nums.length<2) return nums.length;
            //初始化变量
            int i,k=0,result;
            //去除相同的部分
            while(k<nums.length-1 && nums[k]==nums[k+1]) k++;
            //如果全部相同
            if(k==nums.length-1) return 1;
            //确定波动方向
            boolean requireSmall = nums[k] < nums[k + 1];
            //现在，至少有两个了
            result=2;
            for(i = k+1;i<nums.length-1;i++) {
                if(requireSmall){
                    //上升期，增加长度
                    if(nums[i]>nums[i+1]){
                        nums[k + result] = nums[i+1];
                        result++;
                        requireSmall = false;
                    }
                    else{
                        //更新数据
                        nums[k + result - 1] = nums[i + 1];
                    }
                }
                else{
                    //下降期，增加长度
                    if( nums[i] < nums[i + 1]) {
                        nums[k + result] = nums[i + 1];
                        result++;
                        requireSmall = true;
                    }
                    else{
                        //更新数据
                        nums[k + result - 1] = nums[i + 1];
                    }
                }
            }
            //从k -> k+result 是所有的wiggle字符串
            for(i=k;i<k+result;i++) {
                System.out.print(nums[i]+" ");
            }
            System.out.println();
            //返回长度
            return result;
        }
    }

    public static void main(String[] args){
        Solution solution = new Solution();
        System.out.println(solution.wiggleMaxLength(new int[]{1,17,5,10,13,15,10,5,16,8}));
    }
}
